/**
 * @author hzq
 * @description 链表节点
 * @date 2024-11-3
 */
export class LinkedNode<T> {
  /** 节点的值 */
  value: T
  /** 下一个节点的引用，初始值为null */
  next: LinkedNode<T> | null = null
  // 构造函数，传入节点的值
  constructor(value: T) {
    this.value = value
  }
}

/**
 * @author hzq
 * @description 链表
 * @date 2024-11-3
 */
class LinkedList<T> {
  // 定义链表的头节点
  private head: LinkedNode<T> | null = null
  // 定义链表的节点数量
  private count = 0

  /**
   * 获取链表的节点数量
   */
  get size() {
    return this.count
  }

  /**
   * 根据位置获取节点
   * @param position 位置
   * @returns
   */
  private getNode(position: number) {
    let index = 0
    let current = this.head
    // 遍历链表，直到找到指定位置的节点
    while (index++ < position && current) {
      current = current.next
    }
    return current
  }

  /**
   * 在链表末尾添加节点
   * @param value 节点的值
   */
  append(value: T) {
    const newNode = new LinkedNode(value)
    // 如果链表为空，则将新节点设为头节点
    if (!this.head) {
      this.head = newNode
    } else {
      // 否则，遍历链表，找到最后一个节点，将新节点添加到末尾
      let current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = newNode
    }
    this.count++
  }

  /**
   * 在指定位置插入节点
   * @param value 节点的值
   * @param position 位置
   * @returns
   */
  insert(value: T, position: number) {
    // 如果位置小于0或大于链表节点数量，则返回false
    if (position < 0 || position > this.count) {
      return false
    }
    const newNode = new LinkedNode(value)
    // 如果位置为0，则将新节点设为头节点
    if (position === 0) {
      newNode.next = this.head
      this.head = newNode
    } else {
      // 否则，找到指定位置的前一个节点，将新节点插入到该节点之后
      const previous = this.getNode(position - 1)
      newNode.next = previous!.next
      previous!.next = newNode
    }
    this.count++
    return true
  }

  /**
   * 删除指定位置的节点
   * @param position 位置
   * @returns
   */
  removeAt(position: number) {
    // 如果位置小于0或大于等于链表节点数量，则返回undefined
    if (position < 0 || position >= this.count) {
      return void 0
    }
    const current = this.head
    // 如果位置为0，则将头节点指向下一个节点
    if (position === 0) {
      this.head = current?.next ?? null
    } else {
      // 否则，找到指定位置的前一个节点，将前一个节点的next指向下一个节点的next
      const previous = this.getNode(position - 1)
      previous!.next = current?.next?.next ?? null
    }
    this.count--
    return null
  }

  /**
   * 删除指定值的节点
   * @param value 节点的值
   * @returns
   */
  remove(value: T) {
    // 获取指定值的节点位置
    const index = this.indexOf(value)
    // 删除指定位置的节点
    return this.removeAt(index)
  }

  /**
   * 获取指定位置的节点值
   * @param index 位置
   * @returns
   */
  get(index: number) {
    // 如果位置小于0或大于等于链表节点数量，则返回undefined
    if (index < 0 || index >= this.count) {
      return void 0
    }
    // 获取指定位置的节点
    return this.getNode(index)?.value ?? void 0
  }

  /**
   * 获取指定值的节点位置
   * @param value 节点的值
   * @returns
   */
  indexOf(value: T) {
    let current = this.head
    let index = 0
    // 遍历链表，找到指定值的节点位置
    while (current) {
      if (current.value === value) {
        return index
      }
      current = current.next
      index++
    }
    return -1
  }

  /**
   * 更新指定位置的节点值
   * @param value 节点的值
   * @param position 位置
   * @returns
   */
  update(value: T, position: number) {
    // 如果位置小于0或大于等于链表节点数量，则返回false
    if (position < 0 || position >= this.count) {
      return false
    }
    // 获取指定位置的节点，并更新其值
    const current = this.getNode(position)
    current!.value = value
    return true
  }

  /**
   * 判断链表是否为空
   * @returns
   */
  isEmpty() {
    return this.count === 0
  }

  /**
   * 打印链表
   */
  toString() {
    const values = []
    let current = this.head
    // 遍历链表，将节点值添加到数组中
    while (current) {
      values.push(current.value)
      current = current.next
    }
    // 打印数组
    console.log(values.join(' -> '))
  }
}

export default LinkedList
